import java.io.BufferedWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class ItemsetList {
    /* ======================================================
     * MEMBERS
     * ====================================================== */
    protected TreeMap<String, Itemset> _itemsets;
    private Double _support;
    private TransactionList _masterTransList;
    private Integer _k;

    /* ======================================================
     * CONSTRUCTOR
     * ====================================================== */
    public ItemsetList(Double support, TransactionList t, Integer k){
	_itemsets = new TreeMap<String, Itemset>();
	_support = support;
	_masterTransList = t;
	_k = k;
    }

    /* ======================================================
     * METHODS
     * ====================================================== */
    public void add(Itemset item){
	_itemsets.put(item.hashKey(), item);
    }

    public void addAll(ItemsetList isetList){
	_itemsets.putAll(isetList.getItemsets());
    }
    
    public ItemsetList aprioriGen(){
	// First join the list onto itself
	ItemsetList returnList = this.getJoin();
	// Next, prune the ones that are not in the L-1 ItemsetList
	returnList.pruneCandidates(this);
	return returnList;
    }

    public void calculateSupport(){
	// This function sets the support values for each itemset in the list
	for (String key : _itemsets.keySet()){
	    _itemsets.get(key).setSupport(_itemsets.get(key).numTransactions().doubleValue() / _masterTransList.size().doubleValue());
	}
    }

    public ItemsetList consolidate(ArrayList<ItemsetList> L){
	ItemsetList returnList = new ItemsetList(_support, _masterTransList, _k);
	for (ItemsetList isetList : L){
	    returnList.addAll(isetList);
	}
	return returnList;
    }
    
    public Boolean contains(Itemset item){
	return _itemsets.containsKey(item.hashKey());
    }

    public Boolean contains(String s){
	return _itemsets.containsKey(s);
    }

    public Itemset get(Itemset item){
	return _itemsets.get(item.hashKey());
    }

    public Itemset get(String key){
	return _itemsets.get(key);
    }

    public TreeMap<String, Itemset> getItemsets(){
	return _itemsets;
    }
    
    @SuppressWarnings("unchecked")
    public ArrayList<Itemset> getOrderedItems(){
	ArrayList<Itemset> returnList = new ArrayList<Itemset>();
	for (String key : this.keys()){
	    returnList.add(this.get(key));
	}

	Collections.sort(returnList, new Comparator(){
	    public int compare(Object o1, Object o2){
		Itemset i1 = (Itemset) o1;
		Itemset i2 = (Itemset) o2;
		return i2.getSupport().compareTo(i1.getSupport());
	    }
	});
	return returnList;
    }
    
    public ItemsetList getJoin(){
	ItemsetList returnList = new ItemsetList(_support, _masterTransList, _k+1);
	for(String key : _itemsets.keySet()){
	    // Isolate the itemsets that have items greater than or equal to the current
	    // Itemset. Note, items within the itemset are ordered according to the name of the item
	    // and are stored sorted in the ItemsetList
	    SortedMap<String, Itemset> sublist = this._itemsets.tailMap(key, false);

	    // For k > 1, make sure you only join on those itemsets in which the first k - 1
	    // items are equal.
	    if (this.kValue() > 1){
		for (String s : sublist.keySet()) {
		    Itemset currIset = sublist.get(s);
		    if (currIset.contains(_itemsets.get(key).sublist(0, _k-1))){
			// if all of the k - 1 items are equal, create a new Itemset, add
			// all k items in it from the current ItemsetList, and append the
			// k - 1 item from the sublist to it.
			Itemset i = new Itemset(_itemsets.get(key).sublist(0, _k));
			i.addItem(currIset.getItem(_k-1));
			returnList.add(i);
		    }
		    else {
			break;
		    }
		}
	    }
	    // If k = 1, then just return an ItemsetList of the full join. There is no constraint
	    // that needs to be checked.
	    else {
		for (String s : sublist.keySet()) {
		    Itemset i = new Itemset(_itemsets.get(key).getItem(0));
		    i.addItem(sublist.get(s).getItem(0));
		    returnList.add(i);
		}
	    }
	}
	return returnList;
    }

    public Double getSupport(){
	return _support;
    }

    public void incrementCandidates(Transaction t){
	// Loop through the ItemsetList and return those itemsets that are contained
	// within this transaction
	for (String key : _itemsets.keySet()){
	    Boolean flag = true;
	    // Loop through each item that is in the itemset
	    for (Integer i = 0; i < _itemsets.get(key).size(); i++){
		if (!t.getItems().contains(_itemsets.get(key).getItem(i))) {
		    flag = false;
		    break;
		}
	    }
	    if (flag.equals(true)){
		_itemsets.get(key).addTransaction(t);
	    }
	}
    }

    public Boolean isEmpty(){
	if (this.size() == 0){
	    return true;
	}
	else {
	    return false;
	}
    }

    public Integer kValue(){
	return _k;
    }

    public Set<String> keys(){
	return _itemsets.keySet();
    }

    public void print(){
	System.out.println(String.format("Support: %f", _support));
	for (String s : _itemsets.keySet()){
	    System.out.println(String.format("%s", s));
	}
    }

    @SuppressWarnings("unchecked")
    public void printAssociationRules(Double minConf, BufferedWriter out) throws IOException{
	//This function prints out the association rules that meet the minimum confidence
	ArrayList<AssociationRule> assocRules = new ArrayList<AssociationRule>();
	for (String key : this.keys()){
	    Itemset iset = this.get(key);
	    if (iset.size() > 1){
		for (Integer i = 0; i < iset.getItems().size(); i++){
		    // Set the LHS equal to the current itemset minus the i'th item
		    Itemset LHS = new Itemset(iset.getItems());
		    LHS.getItems().remove(LHS.getItems().get(i));
		    
		    // The RHS is the i'th item
		    Itemset RHS = new Itemset(iset.getItems().get(i));
		    
		    // Get the intersection of all transactions that contain the LHS and RHS
		    ArrayList<Transaction> transIntersection = new ArrayList<Transaction>();
		    transIntersection.addAll(this.get(LHS).getTransactions());
		    transIntersection.retainAll(this.get(RHS).getTransactions());
		    
		    // The confidence is the size of the intersection of the LHS and RHS divided by the number of transactions
		    // of the LHS
		    Double confidence = transIntersection.size() / this.get(LHS).numTransactions().doubleValue();
		    if (confidence >= minConf){
			//out.write(LHS.toString() + " => " + RHS.toString()+ String.format("(Conf: %f%%, Supp: %f%%)", 100 * confidence, 100 * iset.getSupport()));
			//out.newLine();
			assocRules.add(new AssociationRule(confidence, LHS.toString() + " => " + RHS.toString()+ String.format("(Conf: %f%%, Supp: %f%%)", 100 * confidence, 100 * iset.getSupport())));
		    }
		}
	    }
	}
	
	Collections.sort(assocRules, new Comparator(){
	    public int compare(Object o1, Object o2){
		AssociationRule i1 = (AssociationRule) o1;
		AssociationRule i2 = (AssociationRule) o2;
		return i2.getConfidence().compareTo(i1.getConfidence());
	    }
	});
	
	for (Integer i = 0; i < assocRules.size(); i++){
	    out.write(assocRules.get(i).getRule());
	    out.newLine();
	}
    }

    public void prune(){
	// This procedure prunes all of the itemsets that don't meet the minimum support
	TreeMap<String, Itemset> temp = new TreeMap<String, Itemset>();

	for (String key : _itemsets.keySet()){
	    if (_itemsets.get(key).getSupport() >= _support){
		temp.put(key, _itemsets.get(key));
	    }
	}
	_itemsets = temp;
    }

    public void pruneCandidates(ItemsetList kMinusOneList){
	// This procedure prunes the candidates that do not have each k - 1 subset in
	// the L(k - 1) list
	TreeMap<String, Itemset> temp = new TreeMap<String, Itemset>();
	temp.putAll(_itemsets);
	for(String key : _itemsets.keySet()){
	    for(String subset : _itemsets.get(key).getKMinus1Subsets()){
		if (!kMinusOneList.contains(subset)) {
		    temp.remove(key);
		    continue;
		}
	    }
	}
	_itemsets = temp;
    }

    public Integer size(){
	return _itemsets.size();
    }

    /* ======================================================
     * CLASSES
     * ====================================================== */
    public class AssociationRule{
	Double _confidence;
	String _rule;
	
	public AssociationRule(Double c, String r){
	    _confidence = c;
	    _rule = r;
	}
	
	public Double getConfidence(){
	    return _confidence;
	}
	
	public String getRule(){
	    return _rule;
	}
    }
}
